package org.example.myleet.p1711;

import java.util.*;

public class Solution {
    public int countPairs(int[] deliciousness) {
        int mod = 1000000007;
        int[] targets = new int[32];
        targets[0] = 1;
        for (int i = 1; i < 32; ++i) {
            targets[i] = targets[i - 1] * 2;
        }
        //存放餐食美味程度计数的map
        Map<Integer, Integer> dishCountMap = new HashMap<>();
        for (int dish : deliciousness) {
            //预处理，统计各种美味程度的餐食数量
            int dishCount = dishCountMap.getOrDefault(dish, 0);
            ++dishCount;
            dishCountMap.put(dish, dishCount);
        }
        List<Integer> dishes = new ArrayList<>(dishCountMap.keySet());
        long count = 0L;
        for (int dish : dishes) {
            int dishCount = dishCountMap.get(dish);
            //在2^32内查找大餐，实测评分中可以缩小到22，会更快
            for (int j = 0; j < 32; ++j) {
                //通过相减找组成大餐的另一个餐食，找不到都continue
                int secondDish = targets[j] - dish;
                if (0 > secondDish) {
                    continue;
                }
                Integer secondDishCount = dishCountMap.get(secondDish);
                if (null == secondDishCount) {
                    continue;
                }
                //找到另一个餐食，计算组成餐食的方案数
                long ways;
                if (dish == secondDish) {
                    //如果是相同美味程度的餐食，则按等差数列求和算
                    ways = (long) dishCount * (long) (dishCount - 1) / 2;
                } else {
                    //如果是美味程度不相同的餐食，则按照相乘原理计算方案数
                    ways = (long) dishCount * (long) secondDishCount;
                }
                //大餐
                count += ways;
                count %= mod;
                //已经访问过这个餐食，移除
                dishCountMap.remove(dish);
            }
        }
        return (int) count;
    }
}
